/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/linked-list-cycle-ii
   @Language: C++
   @Datetime: 17-04-07 11:40
   */

/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */

class Solution {
public:
	/**
	 * @param head: The first node of linked list.
	 * @return: The node where the cycle begins. 
	 *           if there is no cycle, return null
	 * Tip: p step 1, q step 2.
	 * Assume l: length of head to first cycle node
	 *        k: length of first cycle node to meeting node
	 *        c: cycle length
	 * then 2*(l+k) = l+n*c+k, n=1,2,3,...
	 * ===> l = n*c-k
	 * let p continue traversal from meeting node, by step 1
	 * and q restart from head by step 1,
	 * they must meet at first cycle node.
	 *
	 * sketch: 1->2->3->4->5-    head=1, first cyle node=3
	 *               ^------'
	 * init p=q=1, q && q->next, do :
	 * q=q->next->next=3, p=p->next=2, not equal, loop
	 * q=q->next->next=5, p=p->next=3, not equal, loop
	 * q=q->next->next=4, p=p->next=4, equal, break.
	 * now, p=q=4.
	 * retraversal, q=head=1, p=p=4, both step is 1
	 * ........     p=3, q=3, find first cycle node 3.
	 */
	ListNode *detectCycle(ListNode *head) {
		// write your code here
		ListNode *p, H(-1);
		for(H.next=head, p=&H; p && p->next; head=head->next){
			p = p->next->next;
			if (p==head) break;
		}
		if (!p || !(p->next)) return NULL;
		for(p=&H; (p=p->next) != (head=head->next););
		return p;
	}
};
